#include<iostream>
#include<vector>
#include<random>
#include<ctime>
using namespace std;

template <typename Comparable>
void sort(vector<Comparable>& A);

template <typename Comparable>
void insertion_sort(vector<Comparable>& A){
    for(int i=1;i<A.size();++i){
        Comparable tmp = move( A[i] );
        int j;
        for( j = i; j > 0 && tmp < A[j-1]; --j){
            A[j] = move(A[j - 1]);
        }
        A[j]=move( tmp );
    }
}

template <typename Comparable>
int partition(vector<Comparable>& A, int left, int right) {
    int i = left, j = right;
    int tmp = A[left];
    while (i < j) {
        while (i < j && A[j] > tmp)
            j--;
        if (i < j) {
            A[i] = A[j];
            i++;
        }
        while (i < j && A[i] < tmp)
            i++;
        if (i < j) {
            A[j] = A[i];
            j--;
        }
    }
    A[i] = tmp;
    return i;
}
template <typename Comparable>
void quick_sort(vector<Comparable>& A, int left, int right) {
    if(left > right)
        return;
    int j = partition(A, left, right);
    quick_sort(A, left, j - 1);
    quick_sort(A, j + 1, right);
    
}

template <typename Comparable>
const Comparable & median3sort(vector<Comparable>& A, int left, int right){
    int center = (left + right)/2;
    if(A[center] < A[left]){
        swap( A[left] , A[center]);
    }
    if(A[right] < A[left]){
        swap( A[left] , A[right]);
    }
    if(A[right] < A[center]){
        swap( A[center] , A[right]);
    }
    swap( A[center], A[right - 1]);
    return A[right - 1];
}
